package interview.sameonebits;

public class SameOneBits {
	public int nextLargest(int n) {
		if(n < 0) {
			return -1;
		}
		
		if(n == 0) {
			return 0;
		}
		
		boolean seenOne = false;
		int mask = 1;
		while(!seenOne) {
			if((n & mask) > 0) {
				seenOne = true;
			} else {
				mask <<= 1;
			}
		}
		
		while((n & mask) > 0) {
			mask <<= 1;
		}
		
		n |= mask;
		n &= ~(mask >> 1);
		
		mask--;
		int m = n & mask;
		while((m & 0x1) == 0) {
			m >>= 1;
		}
		
		n &= ~mask;
		n += m;
		
		return n;
	}

	public int nextSmallest(int n) {
		if(n < 0) {
			return -1;
		}
		
		if(n == 0) {
			return 0;
		}
		
		boolean seenZero = false;
		int mask = 1;
		
		while(!seenZero) {
			if((n & mask) == 0) {
				seenZero = true;
			} else {
				mask <<= 1;
			}
		}
		
		while((n & mask) == 0) {
			mask <<= 1;
		}
		
		n &= ~mask;
		n |= (mask >> 1);
		
		mask >>= 1;
		
		int m = n & (mask - 1);
		n &= ~(mask - 1);
		
		mask >>= 1;
		while((m & mask) == 0) {
			m <<= 1;
		}
		
		n +=m;
		
		return n;
	}
}
